﻿#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
// hoare
// [left, right]
int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		// 右边找⼩
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		// 左边找⼤
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}
// 前后指针
int PartSort2(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}
typedef struct
{
	int leftKeyi;
	int rightKeyi;
}KeyWayIndex;

// 三路划分
KeyWayIndex PartSort3Way(int* a, int left, int right)
{
	int key = a[left];
	// left和right指向就是跟key相等的区间
	// [开始, left-1][left, right][right+1, 结束]
	int cur = left + 1;
	while (cur <= right)
	{
		// 1、cur遇到⽐key⼩，⼩的换到左边，同时把key换到中间位置
		// 2、cur遇到⽐key⼤，⼤的换到右边
		if (a[cur] < key)
		{
			Swap(&a[cur], &a[left]);
			++cur;
			++left;
		}
		else if (a[cur] > key)
		{
			Swap(&a[cur], &a[right]);
			--right;
		}
		else
		{
			++cur;
		}
	}
	KeyWayIndex kwi;
	kwi.leftKeyi = left;
	kwi.rightKeyi = right;
	return kwi;
}
void TestPartSort1()
{
	int a1[] = { 6,1,7,6,6,6,4,9 };
	int a2[] = { 3,2,3,3,3,3,2,3 };
	int a3[] = { 2,2,2,2,2,2,2,2 };
	PrintArray(a1, sizeof(a1) / sizeof(int));
	int keyi1 = PartSort1(a1, 0, sizeof(a1) / sizeof(int) - 1);
	PrintArray(a1, sizeof(a1) / sizeof(int));
	printf("hoare keyi:%d\n\n", keyi1);
	PrintArray(a2, sizeof(a2) / sizeof(int));
	int keyi2 = PartSort1(a2, 0, sizeof(a2) / sizeof(int) - 1);
	PrintArray(a2, sizeof(a2) / sizeof(int));
	printf("hoare keyi:%d\n\n", keyi2);
	PrintArray(a3, sizeof(a3) / sizeof(int));
	int keyi3 = PartSort1(a3, 0, sizeof(a3) / sizeof(int) - 1);
	PrintArray(a3, sizeof(a3) / sizeof(int));
	printf("hoare keyi:%d\n\n", keyi3);
}
void TestPartSort2()
{
	int a1[] = { 6,1,7,6,6,6,4,9 };
	int a2[] = { 3,2,3,3,3,3,2,3 };
	int a3[] = { 2,2,2,2,2,2,2,2 };
	PrintArray(a1, sizeof(a1) / sizeof(int));
	int keyi1 = PartSort2(a1, 0, sizeof(a1) / sizeof(int) - 1);
	PrintArray(a1, sizeof(a1) / sizeof(int));
	printf("前后指针 keyi:%d\n\n", keyi1);
	PrintArray(a2, sizeof(a2) / sizeof(int));
	int keyi2 = PartSort2(a2, 0, sizeof(a2) / sizeof(int) - 1);
	PrintArray(a2, sizeof(a2) / sizeof(int));
	printf("前后指针 keyi:%d\n\n", keyi2);
	PrintArray(a3, sizeof(a3) / sizeof(int));
	int keyi3 = PartSort2(a3, 0, sizeof(a3) / sizeof(int) - 1);
	PrintArray(a3, sizeof(a3) / sizeof(int));
	printf("前后指针 keyi:%d\n\n", keyi3);
}
void TestPartSort3()
{
	//int a0[] = { 6,1,2,7,9,3,4,5,10,4 };
	int a1[] = { 6,1,7,6,6,6,4,9 };
	int a2[] = { 3,2,3,3,3,3,2,3 };
	int a3[] = { 2,2,2,2,2,2,2,2 };
	PrintArray(a1, sizeof(a1) / sizeof(int));
	KeyWayIndex kwi1 = PartSort3Way(a1, 0, sizeof(a1) / sizeof(int) - 1);
	PrintArray(a1, sizeof(a1) / sizeof(int));
	printf("3Way keyi:%d,%d\n\n", kwi1.leftKeyi, kwi1.rightKeyi);
	PrintArray(a2, sizeof(a2) / sizeof(int));
	KeyWayIndex kwi2 = PartSort3Way(a2, 0, sizeof(a2) / sizeof(int) - 1);
	PrintArray(a2, sizeof(a2) / sizeof(int));
	printf("3Way keyi:%d,%d\n\n", kwi2.leftKeyi, kwi2.rightKeyi);
	PrintArray(a3, sizeof(a3) / sizeof(int));
	KeyWayIndex kwi3 = PartSort3Way(a3, 0, sizeof(a3) / sizeof(int) - 1);
	PrintArray(a3, sizeof(a3) / sizeof(int));
	printf("3Way keyi:%d,%d\n\n", kwi3.leftKeyi, kwi3.rightKeyi);
}
//int main()
//{
//	TestPartSort1();
//	TestPartSort2();
//	TestPartSort3();
//	return 0;
//}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	// 随机选key
	int randi = left + (rand() % (right - left));
	Swap(&a[left], &a[randi]);
	// 三路划分
	// left和right指向就是跟key相等的区间
    // [begin, left-1] [left, right] right+1, end]
	int key = a[left];
	int cur = left + 1;
	while (cur <= right)
	{
		// 1、cur遇到⽐key⼩，⼩的换到左边，同时把key换到中间位置
		// 2、cur遇到⽐key⼤，⼤的换到右边
		if (a[cur] < key)
		{
			Swap(&a[cur], &a[left]);
			++left;
			++cur;
		}
		else if (a[cur] > key)
		{
			Swap(&a[cur], &a[right]);
			--right;
		}
		else
		{
			++cur;
		}
	}
	// [begin, left-1] [left, right] right+1, end]
	QuickSort(a, begin, left - 1);
	QuickSort(a, right + 1, end);
}

//int* sortArray(int* nums, int numsSize, int* returnSize) {
//	srand(time(0));
//	QuickSort(nums, 0, numsSize - 1);
//	*returnSize = numsSize;
//	return nums;
//}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 选出左右孩⼦中⼤的那⼀个
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	// 建堆 -- 向下调整建堆 -- O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	// ⾃⼰先实现 -- O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		--end;
	}
}
void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = a[i];
		// 将tmp插⼊到[0,end]区间中，保持有序
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{
	if (left >= right)
		return;
	// 数组⻓度⼩于16的⼩数组，换为插⼊排序，简单递归次数
	if (right - left + 1 < 16)
	{
		InsertSort(a + left, right - left + 1);
		return;
	}
	// 当深度超过2*logN时改⽤堆排序
	if (depth > defaultDepth)
	{
		HeapSort(a + left, right - left + 1);
		return;
	}
	depth++;
	int begin = left;
	int end = right;
	// 随机选key
	int randi = left + (rand() % (right - left));
	Swap(&a[left], &a[randi]);
	int prev = left;
	int cur = prev + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	// [begin, keyi-1] keyi [keyi+1, end]
	IntroSort(a, begin, keyi - 1, depth, defaultDepth);
	IntroSort(a, keyi + 1, end, depth, defaultDepth);
}
void QuickSort(int* a, int left, int right)
{
	int depth = 0;
	int logn = 0;
	int N = right - left + 1;
	for (int i = 1; i < N; i *= 2)
	{
		logn++;
	}
	// introspective sort -- ⾃省排序
	IntroSort(a, left, right, depth, logn * 2);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
	srand(time(0));
	QuickSort(nums, 0, numsSize - 1);
    * returnSize = numsSize;
	return nums;
}